#include <stdio.h>
#include <stdlib.h>

typedef struct _Node {
    int no;
    struct _Node *next;
}*PNode;

PNode init_link_list()
{
    int size = sizeof(struct _Node);
    PNode head = malloc(size);
    head->no = 0;
    head->next = NULL;

    PNode p = head;
    for(int i=1; i<10; ++i) {
        p->next = malloc(size);
        p->next->no = i;
        p = p->next;
    }
    p->next = NULL;
    return head;
}

void print_link_list(PNode head)
{
    PNode p = head;
    while(p!=NULL) {
        printf("%d ", p->no);
        p = p->next;
    }
    printf("\n");
}

PNode reserve_link_list(PNode head)
{
    PNode p = head;
    PNode prev, next;
    prev = NULL;
    while(p != NULL) {
        next = p->next;
        p->next = prev;
        prev = p;
        p = next;
    }
    return prev;
}

PNode intersect_two_link_lists(PNode p1, PNode p2)
{
    if(p1 == NULL) return p2;
    
    PNode head = p1;
    PNode tmp;
    while(p1->next != NULL && p2 != NULL) {
        tmp = p2->next;
        p2->next = p1->next;
        p1->next = p2;
        p1 = p2->next;
        p2 = tmp;
    }
    if(p2 != NULL) p1->next = p2;
    return head;
}

void reorder_link_list(PNode head)
{
    PNode p1 = head;
    PNode p2 = head;
    
    // find middle node
    while(p2 != NULL && p2->next != NULL) {
        p1 = p1->next;
        p2 = p2->next->next;
    }

    // reserve from p1->next to list tail
    p2 = reserve_link_list(p1->next);
    p1->next = NULL;
    p1 = head;

    intersect_two_link_lists(p1, p2);
}

int main()
{
    PNode head = init_link_list();
    print_link_list(head);
    reorder_link_list(head);
    print_link_list(head);

    return 0;
}
